package com.lihepeng.leecode.classic.backtrack;

import org.junit.Test;

/**
 * 使用回溯法
 * 解决迷宫问题
 * 回溯法(backtracking)是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。
 */
public class BackTracking2 {
    private int[][] maze = null;
    private int count = 0;
    private int startI, startJ, endI, endJ;

    private void setStart(int startI, int startJ) {
        this.startI = startI;
        this.startJ = startJ;
    }

    private void setEnd(int endI, int endJ) {
        this.endI = endI;
        this.endJ = endJ;
    }

    public void show() {
        System.out.println("第" + (++count) + "走法");
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[0].length; j++) {
                if (maze[i][j] == 0) {
                    System.out.print(" ");
                } else if (maze[i][j] == 1) {
                    System.out.print("x");
                } else {
                    System.out.println(maze[i][j]);
                }
            }
            System.out.println();
        }
    }
    // 走迷宫，定义起始节点的坐标

    public void play(int x, int y) {
        maze[x][y] = 1;
        // 重点坐标
        if (x == endI && y == endJ) {
            show();
        }
        // 没有走到最终节点
        // 向上走
        if (maze[x][y - 1] == 0) {
            play(x, y - 1);
        }
        // 向下走
        if (maze[x][y + 1] == 0) {
            play(x, y + 1);
        }
        if (maze[x - 1][y] == 0) {
            play(x - 1, y);
        }
        if (maze[x + 1][y] == 0) {
            play(x + 1, y);
        }
        // 当前位置上下左右 都不同，重置节点
        maze[x][y] = 0;
    }

    @Test
    public void runTest() {

    }
}
